<div class="tmd-doc">
<p></p>
<h1 class="tmd-header-1">
No Safe Efficient Ways to Do Three-way String Comparisons in Go
</h1>
<p></p>
<div class="tmd-usual">
Three-way string comparison is widely used in programming (<a href="https://sourcegraph.com/search?q=context:global+switch+strings.Compare+lang:Go+&amp;patternType=literal">proof 1</a> and <a href="https://sourcegraph.com/search?q=context:global+strings.Compare+lang:Go&amp;patternType=standard">proof 2</a>). But up to now (Go 1.19), the <a href="https://github.com/golang/go/blob/go1.19/src/strings/compare.go#L7-L28">strings.Compare</a> function in the standard library is (<a href="https://news.ycombinator.com/item?id=33353106">intentionally</a>) implemented with <a href="https://go-review.googlesource.com/c/go/+/3012">a non-opitimized way</a>:
</div>
<p></p>
<p></p>
<pre class="tmd-code">
<code class="language-Go">func Compare(a, b string) int {
	// NOTE(rsc): This function does NOT call the runtime cmpstring function,
	// because we do not want to provide any performance justification for
	// using strings.Compare. Basically no one should use strings.Compare.
	// As the comment above says, it is here only for symmetry with package bytes.
	// If performance is important, the compiler should be changed to recognize
	// the pattern so that all code doing three-way comparisons, not just code
	// using strings.Compare, can benefit.
	if a == b {
		return 0
	}
	if a &lt; b {
		return -1
	}
	return +1
}
</code></pre>
<p></p>
<div class="tmd-usual">
When comparing two unequal strings, the implementation will perform two comparison operations. Whereas a perfect implementation only needs one, just like the implementation of <a href="https://github.com/golang/go/blob/go1.19/src/bytes/bytes.go#L23-L28">bytes.Compare</a> shown below, in which <a href="https://github.com/golang/go/blob/go1.19/src/internal/bytealg/compare_native.go#L12">bytealg.Compare</a> is implemented using assembly code on most architectures.
</div>
<p></p>
<pre class="tmd-code">
<code class="language-Go">func Compare(a, b []byte) int {
	return bytealg.Compare(a, b)
}
</code></pre>
<p></p>
<div class="tmd-usual">
The <code class="tmd-code-span">strings.Compare</code> implementation is comparatively inefficient. Specifically, it is less efficient when the two string operands are not equal but their lengths are equal.
</div>
<p></p>
<p></p>
<div class="tmd-usual">
Benchmark code constantly shows <code class="tmd-code-span">strings.Compare</code> uses 2x CPU time of <code class="tmd-code-span">bytes.Compare</code> when comparing unequal same-length byte sequences (we view both strings and byte slices as byte sequences here).
</div>
<p></p>
<div class="tmd-usual">
The internal comment for the current <code class="tmd-code-span">strings.Compare</code> implementation is some interesting. The comment suggests that we should not use <code class="tmd-code-span">strings.Compare</code> in Go at all, but no alternative efficient ways are available now yet (ironically, this function is used in <a href="https://github.com/golang/go/blob/go1.19/src/cmd/go/internal/modindex/read.go#L822">Go toolchain code</a> and recommended by <a href="https://github.com/golang/go/blob/go1.19/src/sort/search.go#L88-L99">a standard library function</a>). It mentions that the compiler should make special optimizations to automatically convert the code using comparison operators into internal optimized three-way comparisons if possible. However, such compiler optimizations have never been made, and there are no plans to make such optimizations yet as far as I know. Personally, I doubt such optimizations are feasible to be made for every use case. So I think <a href="https://github.com/golang/go/issues/50167">the <code class="tmd-code-span">strings.Compare</code> should be implemented efficiently</a>, to avoid breaking user expectations.
</div>
<p></p>
<p></p>
<hr  class="tmd-seperator"/>
<p></p>
<div class="tmd-usual">
<span class="tmd-italic">(This is one of 101+ facts and suggestions mentioned in the </span><a href="https://go101.org/optimizations/101.html"><span class="tmd-italic">Go Optimizations 101</span></a><span class="tmd-italic"> book.)</span>
</div>
<p></p>
<p></p>
<div class="tmd-usual">
Update: view discussions on <a href="https://old.reddit.com/r/programming/comments/ycz0va/no_safe_efficient_ways_to_do_threeway_string/">reddit</a> and <a href="https://news.ycombinator.com/item?id=33316402">HN</a>.
</div>
<p></p>
<p></p>
<div class="tmd-usual">
Update 2: finally, the <code class="tmd-code-span">strings.Compare</code> function <a href="https://github.com/golang/go/commit/fd999fda5941f215ef082c6ef70e44e648db5485">got optimizted in Go 1.23</a>.
</div>
<p></p>
<p></p>
</div>
